package LimitedTimeGame.Day_0202;

/**
 * @author zxc
 * @date 2023/02/02 12:42
 **/

/**
 * 题目 ：和大于等于target的最短子数组
 * 题目详述 ：
 * 给定一个含有n个正整数的数组和一个正整数 target 。
 * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。
 * 如果不存在符合条件的子数组，返回 0 。
 *
 * 提示：
 * 1 <= target <= 109
 * 1 <= nums.length <= 105
 * 1 <= nums[i] <= 105
 *
 */
public class MinSubArrayLen {
    /**
     * 思路 ：
     * 即，辅助数组dp来存储 数组nums中下标为0 ~ n的元素和;
     * nums[i...j]（子数组元素和） = dp[j] - dp[i];
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {
        int len = nums.length;
        // dp[i]，即用来存储nums数组中下标 0 ~ i-1的元素和;
        int[] dp = new int[len + 1];
        int sum = 0;
        for(int i = 0 ; i < len ; i++){
            sum += nums[i];
            dp[i + 1] = sum;
        }

        int minLength = len + 1;
        for(int i = 1 ; i <= len ; i++){
            if(dp[i] >= target){
                // dp[j]的初始值为空值
                for(int j = 0 ; j < i ; j++){
                    if(dp[i] - dp[j] >= target){
                        minLength = Math.min(minLength , i - j);
                    }
                }
            }
        }
        return minLength == len + 1 ? 0 : minLength;
    }
}
